// Victor Freire 12/07/09
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <Python.h>

#define PI	   3.14159265358979323846
#define PI_180 0.01745329251994329576	/* PI/180 */
#define ANGLE180_PI 57.29577951308232087684  /* 180/PI */

#define CUBE_SIZE 128
#define EMPTY_SPACE '0' // no wall


//TODO: CHANGE MACRO FUNCTIONS TO UPPERCASE!
#ifndef min
#define min(x,y) (((x) < (y)) ? (x) : (y))
#endif
#ifndef max
#define max(x,y) (((x) > (y)) ? (x) : (y))
#endif

#define rad(x) (PI_180 * x)
#define deg(x) (ANGLE180_PI * x)
#define fixangle(x) ((x < 0) ? ((360.0) + (fmod(x, 360.0))) : (fmod(x, 360.0)))

#define Bool int
#define true 1
#define false 0

typedef struct {
	int x, y;
} Point2i;

typedef struct {
	double x, y;
} Point2d;

/*
Cartesian with inverted Y being used.
*/


/* Calculates the correct distance, removes the "fishbowl" distortion */
static double correct_distance(const Point2d *pov, double view_angle, const Point2d *point, double ray_angle, double true_distance)
{
	double view_ray_ang = fixangle((view_angle - ray_angle));  //angle between the view angle and the ray
	return fabs(true_distance * cos(rad(view_ray_ang))); // correct distance
}


static double distance_points_ang(const Point2d *p1, const Point2d *p2, double angle)
{
	double result;
	double halfangle = fmod(angle, 180);
	
	if(halfangle < 45 || halfangle > 135) 
		result = fabs((p1->x - p2->x) / cos(rad(angle)));
	else 
		result = fabs((p1->y - p2->y) / sin(rad(angle)));
	
	return result;
}

static double distance_points(const Point2d *p1, const Point2d *p2)
{
	return sqrt(((p1->x - p2->x) * (p1->x - p2->x)) + ((p1->y - p2->y) * (p1->y - p2->y)));
}
/* Returns the nearest point of the two and the distance to it. 0 means the first is closer and 1 the second is. Valid points have non-negative X. Assumes a positive angle.*/
static PyObject* nearest_point_and_dist(PyObject *self, PyObject *args)
{
	Point2d pov;
	double angle;
	Point2i hi, vi; // horizontal and vertical intersection

	Bool hi_valid, vi_valid;
	double angle_mod, angle_rad;
	double hdist, vdist, truedist;
	Bool nearest_point;
			
	if (!PyArg_ParseTuple(args, "dddiiii", &pov.x, &pov.y, &angle, &hi.x, &hi.y, &vi.x, &vi.y))
		return NULL;

    hi_valid = (hi.x >= 0);
	vi_valid = (vi.x >= 0);
	angle_mod = fmod(angle, 180);
	angle_rad = rad(angle);
    
	if(hi_valid)
	    if((45.0 < angle_mod) && (angle_mod < 135.0))
            hdist = fabs((pov.y - hi.y) / sin(angle_rad));
        else
            hdist = fabs((pov.x - hi.x) / cos(angle_rad));

    if(vi_valid)
	    if((45.0 < angle_mod) && (angle_mod < 135.0))
            vdist = fabs((pov.y - vi.y) / sin(angle_rad));
        else
            vdist = fabs((pov.x - vi.x) / cos(angle_rad));
        
    if(hi_valid && vi_valid)
		if(hdist < vdist) vi_valid = false;
        else hi_valid = false;
	            
	if(hi_valid) {
		nearest_point = false;
        truedist = hdist;
	}
	else {
        nearest_point = true;
        truedist = vdist;
	}
    
    return Py_BuildValue("(id)", nearest_point, truedist);
}

/* Finds the angle of the vector made of two points. The first point is the origin. */
static PyObject* angle_points(PyObject *self, PyObject *args)
{
	Point2d p1, p2;
	double angle;

	if (!PyArg_ParseTuple(args, "dddd", &p1.x, &p1.y, &p2.x, &p2.y))
		return NULL;
	
	if(p1.x == p2.x) angle = (p1.y > p2.y) ? 90.0 : 270.0;
	else if(p1.y == p2.y) angle = (p1.x < p2.x) ? 0.0 : 180.0;
	else {
	/*
		tan for inverted cartesian:
			- - 
			+ +		
	*/
		angle = deg(atan((p1.y - p2.y) / (p1.x - p2.x))); //angle in degrees
		if(p1.x < p2.x)
			if(p1.y < p2.y) angle = 360.0 - angle;
			//else, angle is correct
		else
			if(p1.y < p2.y) angle = 180 + angle;
			else angle = 180 - angle;
	}
				
	return Py_BuildValue("d", angle);
}

static PyObject* Pydistance_points_ang(PyObject *self, PyObject *args)
{
	Point2d p1, p2;
	double angle, dist;
						
	if (!PyArg_ParseTuple(args, "ddddd", &p1.x, &p1.y, &p2.x, &p2.y, &angle))
		return NULL;
	dist = distance_points_ang(&p1, &p2, angle);
	return Py_BuildValue("d", dist);
}


static PyObject* Pydistance_points(PyObject *self, PyObject *args)
{
	Point2d p1, p2;
	double dist;

	if (!PyArg_ParseTuple(args, "dddd", &p1.x, &p1.y, &p2.x, &p2.y))
		return NULL;
	dist = distance_points(&p1, &p2);
	return Py_BuildValue("d", dist);
}

/* Calculates the correct distance, removes the "fishbowl" distortion. */
static PyObject* Pycorrect_distance(PyObject *self, PyObject *args)
{
	Point2d pov;
	double pov_angle, ray_angle, truedist;

	double angle_view_ray, correctdist;   //angle between the view angle and the ray

	if (!PyArg_ParseTuple(args, "ddddd", &pov.x, &pov.y, &pov_angle, &ray_angle, &truedist))
		return NULL;

    angle_view_ray = fixangle(pov_angle - ray_angle);
    correctdist = fabs(truedist * cos(rad(angle_view_ray)));
    
    return Py_BuildValue("d", correctdist);
}

/* 
Calculates the distance and the texture offset of a given object. If the ray hits the object.
Returns the tuple (distance, offset) or None if there weren't any intersections.

MONSTER LINE SEGMENT: (always perpendicular to player view angle)
B ----------- O ------------ A
I is the intersection point
O is the object position
*/ 
static PyObject* object_intersect(PyObject *self, PyObject *args)
{
	Point2d pov, obj;
	double ray_angle, view_angle;
	int obj_width;
	
	Point2d ob_vec, a, b, i;
	double ob_angle, m_ob, m_ra, m_diff;
	double dist, offset, fixed_dist;
					
	if (!PyArg_ParseTuple(args, "ddddddi", &pov.x, &pov.y, &obj.x, &obj.y, &ray_angle, &view_angle, &obj_width))
		return NULL;
		
	ob_angle = ray_angle + 90.0;
	// Transform Y in Cartesian
	pov.y = -pov.y;
	obj.y = -obj.y;
	
	m_ob = tan(rad(ob_angle));
	m_ra = tan(rad(ray_angle));
	
	m_diff = (m_ob - m_ra);
	if(!m_diff) Py_RETURN_NONE; // prevent zero division
	
	// Intersection point coordinates
	i.x = (-m_ra * pov.x + m_ob * obj.x + pov.y - obj.y) / m_diff;
	i.y = m_ra * (i.x - pov.x) + pov.y;

	// Is the intersection point valid?
	//// Get coordinate boundaries for intersection point
	ob_vec.x = (obj_width / 2) * cos(rad(ob_angle));
	ob_vec.y = (obj_width / 2) * sin(rad(ob_angle));
	a.x = obj.x - ob_vec.x;
	a.y = obj.y - ob_vec.y;
	b.x = obj.x + ob_vec.x;
	b.y = obj.y + ob_vec.y;
    
    
	if(!(min(a.x, b.x) <= i.x && i.x <= max(a.x, b.x) && min(a.y, b.y) <= i.y && i.y <= max(a.y, b.y)))
		Py_RETURN_NONE;
	
	if(90.0 < ray_angle && ray_angle < 270.0){
		if(i.x > pov.x) Py_RETURN_NONE;
	} 
	else {
		if(i.x < pov.x) Py_RETURN_NONE;
	}

	dist = distance_points_ang(&i, &pov, ray_angle);
    offset = distance_points_ang(&i, &b, ob_angle);
	
	fixed_dist = correct_distance(&pov, view_angle, &i, ray_angle, dist); // apply fishbowl correction
	
    return Py_BuildValue("dd", fixed_dist, offset);

}

static Point2i togrid(const Point2i *p)
{
	Point2i gridpoint = {p->x >> 7, p->y >> 7};
	return gridpoint;
}

static PyObject* Pytogrid(PyObject *self, PyObject *args)
{
	Point2i pos, grid;
	
	if(!PyArg_ParseTuple(args, "ii", &pos.x, &pos.y))
		return NULL;
	
	grid = togrid(&pos);

	return Py_BuildValue("(ii)", grid.x, grid.y);
	
}

static PyObject* PytogridF(PyObject *self, PyObject *args)
{
	Point2d pos;
	Point2i grid;

	Point2i intpos;
	
	if(!PyArg_ParseTuple(args, "dd", &pos.x, &pos.y))
		return NULL;

	intpos.x = (int)(pos.x);
	intpos.y = (int)(pos.y);
	grid = togrid(&intpos);

	return Py_BuildValue("(ii)", grid.x, grid.y);
	
}

static Bool is_valid_grid(const Point2i *g, const Point2i *bounds)
{
	return (0 <= g->x && g->x < bounds->x) && (0 <= g->y && g->y < bounds->y);
}

//PyList_GetItem(PyObject *list, Py_ssize_t index;
// Py_ssize_t: On a 32-bit system, no code will break, as Py_ssize_t is just a typedef for int.
// http://www.python.org/dev/peps/pep-0353/#specification

static Bool wall_on(const Point2i *p, PyObject *world)
{
	/*
	   def wall_on(self, gridpos):
        ''' Checks for wall on grid coordinates X and Y '''
        return Maps.world[gridpos[1]][gridpos[0]] != '0'
	*/
	//PyObject* PyInt_FromLong(long ival);
	//Py_ssize_t PyInt_AsSsize_t(PyObject *io);
	//Py_ssize_t index = PyInt_AsSsize_t(PyInt_FromLong(p))
	//PyObject* PyObject_GetItem(PyObject *o, PyObject *key)
	//PyObject* PyInt_FromLong(long ival)
	////PyObject *index0 = PyInt_FromLong(p.x);
	////PyObject *index1 = PyInt_FromLong(p.y);
	//long PyInt_AS_LONG(PyObject *io)
	//PyObject* PySequence_GetItem(PyObject *o, Py_ssize_t i)
	//char* PyString_AS_STRING(PyObject *string)
	PyObject *secondlist, *wallstr;
	char *wallsymbol;
	
	secondlist = PySequence_GetItem(world, p->y);
	wallstr = PySequence_GetItem(secondlist, p->x);
	wallsymbol = PyString_AS_STRING(wallstr);
	if(*wallsymbol == EMPTY_SPACE) return false;
	return true;
}

/*
Returns vertical intersection: None if no valid points were hit or the tuple with the wall point hit. 
*/
static PyObject* vertical_intersect(PyObject *self, PyObject *args)
{
	Point2d pos;
	double ray_angle;
	Point2i wbounds; // wbounds
	PyObject *world;
	
	Bool ray_facing_left;
	double ray_angle_rad;
	Point2i fp;	//first_point, 
	Point2d fp_var; // first_point_variation,
	Point2i fp_grid;  // firstpointgrid
	Point2i var; // x_variation and y_variation
	Point2i np; // next_point
	Point2i np_grid; //next_point_grid
	
	if(!PyArg_ParseTuple(args, "dddiiO", &pos.x, &pos.y, &ray_angle, &wbounds.x, &wbounds.y, &world))
		return NULL;

	ray_facing_left = (90.0 < ray_angle && ray_angle < 270.0);		
	ray_angle_rad = rad(ray_angle);
		
	// Finds the X of the first intersection point, then decides whether line belongs to left or right block, do not remove round down
    fp.x = (int)(pos.x / CUBE_SIZE) * CUBE_SIZE;

    if(ray_facing_left)
        fp.x -= 1;         // belongs to left block
    else
        fp.x += CUBE_SIZE; // belongs to right block
	
	// Player Y plus the its distance to first intersection point
    fp_var.y = (pos.x - fp.x) * tan(ray_angle_rad);
    fp.y = (int)(pos.y + fp_var.y);
        
    // Is the first intersection point inside the world?
    fp_grid = togrid(&fp);
    
	if(!is_valid_grid(&fp_grid, &wbounds)) return Py_BuildValue("(ii)", -1, -1); //Py_RETURN_NONE;
	
	// If there's a wall on the first point hit, return the position else continue searching for walls
    if(wall_on(&fp_grid, world)) return Py_BuildValue("(ii)", fp.x, fp.y);
	        
    //Distance between subsequent intersection points
    //The y variation for the next intersections must have the same sign as the first point y variation
    var.y = abs((int)(CUBE_SIZE * tan(ray_angle_rad)));

    if(fp_var.y < 0) var.y = -var.y;

	if(ray_facing_left) var.x = -CUBE_SIZE;
    else var.x = CUBE_SIZE;
	
	// Search for a intersection point until grid index is out of bounds
    np = fp;
    while(1){
        np.x += var.x;
		np.y += var.y;
        np_grid = togrid(&np);
		        
        if(!is_valid_grid(&np_grid, &wbounds)) return Py_BuildValue("(ii)", -1, -1); //Py_RETURN_NONE; // reached end of the world without finding any walls
    	if(wall_on(&np_grid, world)) return Py_BuildValue("(ii)", np.x, np.y);
		 
        //This intersection point does not belong to a wall, proceed to next
    }
}

/*
Returns horizontal intersection: None if no valid points were hit or the tuple with the wall point hit.
*/
static PyObject* horizontal_intersect(PyObject *self, PyObject *args)
{
	Point2d pos;
	double ray_angle;
	Point2i wbounds; // wbounds
	PyObject *world;
	
	Bool ray_facing_up;
	double ray_angle_rad;
	Point2i fp;	//first_point, 
	Point2d fp_var; // first_point_variation,
	Point2i fp_grid;  // firstpointgrid
	Point2i var; // x_variation and y_variation
	Point2i np; // next_point
	Point2i np_grid; //next_point_grid
	
	if(!PyArg_ParseTuple(args, "dddiiO", &pos.x, &pos.y, &ray_angle, &wbounds.x, &wbounds.y, &world))
		return NULL;

	ray_facing_up = (0.0 < ray_angle && ray_angle < 180.0);		
	ray_angle_rad = rad(ray_angle);
		
	// Finds the X of the first intersection point, then decides whether line belongs to left or right block, do not remove round down
    fp.y = (int)(pos.y / CUBE_SIZE) * CUBE_SIZE;

    if(ray_facing_up)
        fp.y -= 1;         // belongs to left block
    else
        fp.y += CUBE_SIZE; // belongs to right block
	
	// Player Y plus the its distance to first intersection point
    fp_var.x = (pos.y - fp.y) / tan(ray_angle_rad);
    fp.x = (int)(pos.x + fp_var.x);
        
    // Is the first intersection point inside the world?
    fp_grid = togrid(&fp);
    
	if(!is_valid_grid(&fp_grid, &wbounds)) return Py_BuildValue("(ii)", -1, -1); //Py_RETURN_NONE;
	
	// If there's a wall on the first point hit, return the position else continue searching for walls
    if(wall_on(&fp_grid, world)) return Py_BuildValue("(ii)", fp.x, fp.y);
	        
    //Distance between subsequent intersection points
    //The y variation for the next intersections must have the same sign as the first point y variation
    var.x = abs((int)(CUBE_SIZE / tan(ray_angle_rad)));

    if(fp_var.x < 0) var.x = -var.x;

	if(ray_facing_up) var.y = -CUBE_SIZE;
    else var.y = CUBE_SIZE;
	
	// Search for a intersection point until grid index is out of bounds
    np = fp;
    while(1){
        np.x += var.x;
		np.y += var.y;
        np_grid = togrid(&np);
		        
        if(!is_valid_grid(&np_grid, &wbounds)) return Py_BuildValue("(ii)", -1, -1); //Py_RETURN_NONE; // reached end of the world without finding any walls
    	if(wall_on(&np_grid, world)) return Py_BuildValue("(ii)", np.x, np.y);
		 
        //This intersection point does not belong to a wall, proceed to next
    }
}

static PyMethodDef methods[] = {
	{"object_intersect", object_intersect, METH_VARARGS, 
	"Calculates the distance and the texture offset of a given object. Returns the tuple (distance, offset) or None if there weren't any intersections."},
	
	{"vertical_intersect", vertical_intersect, METH_VARARGS, 
	"Returns vertical intersection: None if no valid points were hit or the tuple with the wall point hit."},
	
	{"horizontal_intersect", horizontal_intersect, METH_VARARGS, 
	"Returns horizontal intersection: None if no valid points were hit or the tuple with the wall point hit."},
	
	{"distance_points", Pydistance_points, METH_VARARGS, 
	"Returns the distance between two points."},
	
	{"distance_points_ang", Pydistance_points_ang, METH_VARARGS, 
	"Returns the distance between two points using an angle for increased speed."},
	
	{"angle_points", angle_points, METH_VARARGS, 
	"Finds the angle of the vector made of two points. The first point is the origin."},
		
	{"nearest_point_and_dist", nearest_point_and_dist, METH_VARARGS, 
	"Returns the nearest point of the two and the distance to it. 0 means the first is closer and 1 the second is. Valid points have non-negative X. Assumes a positive angle."},

	{"correct_distance", Pycorrect_distance, METH_VARARGS, 
	"Returns the correct distance, removes the fishbowl distortion."},
	
	{"togrid", Pytogrid, METH_VARARGS, 
	"Converts from unit coord to grid coord."},

	{"togridF", PytogridF, METH_VARARGS, 
	"Converts from unit coord to grid coord. Float arguments."},

	{NULL, NULL, 0, NULL} // End of method list
};

PyMODINIT_FUNC initRenderer()
{
    (void) Py_InitModule("Renderer", methods);   
}


	


